
#include <string.h>
#include <stdlib.h>

/* Makes suffix array p of x. x becomes inverse of p. p and x are both of size
   n+1. Contents of x[0...n-1] are integers in the range l...k-1. Original
   contents of x[n] is disregarded, the n-th symbol being regarded as
   end-of-string smaller than all other symbols.*/
void suffixsort(int *x, int *p, int n, int k, int l);

int* build_suffix_array(char* s) {
	int n = strlen(s);
	int l = 0;
	int k = 256;
	int *x = malloc((n+1)*sizeof(int));
	int *p = malloc((n+1)*sizeof(int));
	memset(p,0,n);
	int i=0;
	for (; i<n; ++i) {
		x[i]=s[i];
	}
	suffixsort(x,p,n,k,l);
	free(x);
	// store size in first element
	p[0]=n;
	return p;
}

int* build_suffix_array_int(int* s) {
	int n = s[0];
	int l = 0;
	int k = 256;
	int *p = malloc((n+1)*sizeof(int));
	memset(p,0,n);
	suffixsort(s+1,p,n,k,l);
	// store size in first element
	p[0]=n;
	return p;
}

int* alloc_array(int size) {
	int *x = malloc((size+1)*sizeof(int));
	memset(x,0,size+1);
	x[0]=size;
	return x;
}

void free_array(int* p) {
	free(p);
}

int get(int* p, int i) {
	if (p==NULL) return -1;
	if (i+1>p[0]) return -1;
	if (i<0) return -1;
	return p[i+1];
}

void set(int* p, int i, int value) {
	if (p==NULL) return;
	if (i+1>p[0]) return;
	if (i<0) return;
	p[i+1]=value;
}
